import java.util.Arrays;

public class binarySearchBasic {
    //二分查找 黑马
    public static int binarySearchBasicA(int[] a,int target) {
        //定义两个变量用于存储下标
        int i = 0;
        int j = a.length - 1;
        while(i <= j) {
            int m = (i + j) >> 1;
            if (target < a[m]) {
                j = m - 1;
            } else if(a[m] < target ) {
                i = m + 1;
            } else {
                return m;
            }
        }
        return -1;

    }
    //改动版
    //j 值作为一个边界值 j 所指向的对象一定不是我们的查找目标
    public static int binarySearchBasicB(int[] a,int target) {
        //定义两个变量用于存储下标
        int i = 0;
        int j = a.length;
        while(i < j) {
            int m = (i + j) >> 1;
            if (target < a[m]) {
                j = m;
            } else if(a[m] < target ) {
                i = m + 1;
            } else {
                return m;
            }
        }
        return -1;

    }
//再度优化
    public static int binarySearchBasicC(int[] a,int target) {
        //定义两个变量用于存储下标
        int i = 0;
        int j = a.length;
        while(1 < j - i) {
            int m = (i + j) >> 1;
            if (target < a[m]) {
                j = m;
            } else {
                i = m;
            }
        }
        if (a[i] == target) {
            return i;
        } else {
            return -1;
        }
    }

    public static void test() {
        int[] a = {2,5,8};
        int target = 4;

        int i = Arrays.binarySearch(a, target);

        if (i < 0) {
            int insertIndex = Math.abs(i + 1);
            int[] b = new int[a.length + 1];
            System.arraycopy(a, 0, b, 0, insertIndex);
            b[insertIndex] = target;
            System.arraycopy(a, insertIndex, b, insertIndex + 1, a.length-insertIndex);
            a = b;
            System.out.println(Arrays.toString(b));
        }
    }


    //在查找的元素重复的情况下找到最左侧的哪一个
    //没找到的情况下返回比目标大的并且最靠左的索引位置
    public static int binarySearchBasicD(int[] a,int target) {
        //定义两个变量用于存储下标
        int candidate = -1;
        int i = 0;
        int j = a.length;
        while (i < j) {
            int m = (i + j) >> 1;
            if (a[m] < target) {
                i = m + 1;
            } else if (target < a[m]) {
                j = m - 1;
            } else {
                candidate = m;
                j = m - 1;
            }
        }
        return candidate;
    }

    public static int binarySearchBasicE(int[] a,int target) {

        int i = 0;
        int j = a.length-1;
        while(i <= j) {
            int m = (i + j) >> 2;
            if (target <= a[m]) {
                j = m-1;
            } else {
                i = m + 1;
            }
        }
        return i;
    }

    public static int binarySearchRightMost(int[] a,int target) {

        int i = 0;
        int j = a.length-1;
        int candidate = -1;
        while(i <= j) {
            int m = (i + j) >> 2;
            if (target <= a[m]) {
                j = m-1;
            } else if(a[m] < target){
                i = m + 1;
            } else {
                candidate = m;
                i = m + 1;
            }
        }

        return candidate;
    }

    //比目标小的并且最靠右的数
    public static int binarySearchRightMost2(int[] a,int target) {

        int i = 0;
        int j = a.length-1;
        while(i <= j) {
            int m = (i + j) >> 1;
            if (target < a[m]) {
                j = m-1;
            } else {
                i = m + 1;
            }
        }

        return i - 1;
    }


    //力扣 704 二分查找
    public int search (int[] a, int target) {
        int i = 0;
        int j = a.length;
        while ( i < j) {
            int m = (i + j) >> 1;
            if (target < a[m]) {
                j = m;
            } else if (a[m] > target){
                i = m + 1;
            } else {
                return m;
            }
        }
        return -1;
    }

    //力扣35 收缩插入位置

    //力扣36 在排序数组中查找元素的第一个和最后一个
    public int[] searchRange (int[] a , int target) {
        int x = left(a, target);
        if (x == -1) {
            return new int[]{-1, -1};
        } else {
            return new int[]{x, right(a, target)};
        }
    }

    public int left(int[] a, int target) {
        int i = 0, j = a.length-1;
        int candidate = -1;
        while(i <= j) {
            int m = (i + j) >>> 1;
            if (target < a[m]) {
                j = m - 1;
            } else if(a[m] < target) {
                i = m + 1;
            } else {
                candidate = m;
                j = m - 1;
            }
        }
        return candidate;
    }

    public int right(int[] a, int target) {
        int i = 0, j = a.length-1;
        int candidate = -1;
        while(i <= j) {
            int m = (i + j) >>> 1;
            if (target < a[m]) {
                j = m - 1;
            } else if(a[m] < target) {
                i = m + 1;
            } else {
                candidate = m;
                i = m + 1;
            }
        }
        return candidate;
    }
    public static void main(String[] args) {
        test();
    }
}
